#include "List.h"

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        //非递归做法
        //ListNode* tail = NULL, * p = head;
        //while (p)
        //{
        //    auto t = p->next; //记录链表的下一个结点
        //    p->next = tail;
        //    tail = p;
        //    p = t;
        //}
        //return tail;

        //递归做法
        //做法：先记录当前结点的下一个结点 然后利用递归函数，将其后面的部分反转，然后把原结点接在之前记录的结点后面
        if (head == NULL || head->next == NULL) return head;
        ListNode* tail = head->next;
        ListNode* newnode = reverseList(head->next); //将其后面的结点进行翻转
        head->next = tail->next;
        tail->next = head;
        return newnode; //返回反转后的头节点
    }
};